A skip list is a probabilistic data structure used for referencing an ordered list of stored elements and includes nodes that correspond to the respective elements. The purpose of a skip list is to reference the respective elements in a manner that enables a user to quickly locate a particular element. A skip list 200 is shown in FIG. 2A, which contains a number of skip list levels 202. Each level is an ordered linked list of nodes 204 containing a subsequence of the nodes in the linked list of the level below. The bottom level (Level 0) contains all the nodes in the skip list, namely 1, 3, 5, 7, 12, 13, 17, 20 and 21. The decision of whether a node 204 of any given level appears also in the level above this level, is usually made on the basis of a fixed probability. Commonly used values for this probability are 0.25 and 0.5, but any probability can be used. The probability used affects the performance of the skip list.
A search for a node within the skip list starts from the top left corner 206 and moves in the direction of the bottom right corner 208 of the skip list 200. The search is effected by comparing the element that the user is searching for with the nodes of the highest level. In the case of skip list 200, the highest level is level 2. If, for example, a user is trying to locate the element 20, the user firstly compares 20 with the node 7 on level 2, which is the closest to the top left corner 206 of skip list 200. Since 20 is larger than 7, the search continues and 20 is next compared with the second node on level 2, which is of the value of 17. Since the node 17 is also the last one on the level 2 and the element 20 is still larger than this node, the search moves to the lower level 1 and to the right of the node 17. Here the next node is the node 20, which is identical with the element 20. Accordingly, the element 20 is located and the search is terminated. The multi-level structure of the skip list 200 allows more efficient searching to be effected than with the case of simply comparing the element with every single node.
A skip list with a finite number of levels only works efficiently with a limited number of nodes. Once the skip list contains a certain number of nodes, then adding further nodes degrades the performance of the skip list and logarithmic asymptotic complexity, typical for most skip lists, is not maintained. This is a well known limitation of skip lists. This problem also affects deterministic skip lists, in which the decision to promote a node to a higher level is based not on a probability, but on a specific rule.
A common solution to this problem is to increase the number of levels in the skip list. This may not be possible for some skip lists since the increased size of some of the nodes results in an unacceptable memory footprint. This is particularly relevant to a dynamic memory manager which often utilises the so called memory “free list”. The free lists are usually used for tracking free memory blocks of limited sizes in which, for efficiency reasons, the skip list nodes themselves are often stored. Thus, the total number of levels of the skip list (also referred to as a plurality of linked lists of the skip list) is constrained by an available size of at least one of the memory blocks referenced by the skip list.
A modified skip list has been developed to overcome the problems created by having a finite number of levels. However, the modified skip list results in additional computations required when searching the list.
Another solution, when an upper bound on the number of nodes in the skip list is known in advance, is to choose a probability value suitable to the particular number of nodes. However, in many cases, such the case of a dynamic memory manager, the number of nodes to be stored is not known in advance and is highly variable. In addition, choosing a probability value that supports a large number of nodes will decrease the performance of the skip list in the cases with a lower number of nodes.
It is an object of the present invention to substantially overcome, or at least ameliorate, one or more disadvantages of existing arrangements or to offer a useful alternative.